/*
 * @lc app=leetcode.cn id=1356 lang=javascript
 *
 * [1356] 根据数字二进制下 1 的数目排序
 */

// @lc code=start
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var sortByBits = function (arr) {
  // 计算二进制1的数量
  function getBit(n) {
    let result = 0;
    while (n !== 0) {
      result += n % 2;
      n = Math.floor(n / 2);
    }
    return result;
  }

  const list = [...arr];
  const bits = new Map();

  for (let i = 0; i < list.length; i++) {
    bits.set(list[i], getBit(list[i]));
  }
  list.sort((a, b) => {
    if (bits.get(a) !== bits.get(b)) {
      return bits.get(a) - bits.get(b);
    } else {
      return a - b;
    }
  });

  return list;
};
// @lc code=end

/**
 * 时间复杂度：O(nlog⁡n)，其中 n 为整数数组 arr 的长度
 * 空间复杂度：O(n)，其中 n 为整数数组 arr 的长度
 */
